{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Restricted Paths From First to Last Node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort #dynamic-programming #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序 #动态规划 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countRestrictedPaths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从第一个节点出发到最后一个节点的受限路径数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一个加权无向连通图。给你一个正整数 <code>n</code> ，表示图中有 <code>n</code> 个节点，并按从 <code>1</code> 到 <code>n</code> 给节点编号；另给你一个数组 <code>edges</code> ，其中每个 <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>, weight<sub>i</sub>]</code> 表示存在一条位于节点 <code>u<sub>i</sub></code> 和 <code>v<sub>i</sub></code> 之间的边，这条边的权重为 <code>weight<sub>i</sub></code> 。</p>\n",
    "\n",
    "<p>从节点 <code>start</code> 出发到节点 <code>end</code> 的路径是一个形如 <code>[z<sub>0</sub>, z<sub>1</sub>,<sub> </sub>z<sub>2</sub>, ..., z<sub>k</sub>]</code> 的节点序列，满足 <code>z<sub>0 </sub>= start</code> 、<code>z<sub>k</sub> = end</code> 且在所有符合 <code>0 <= i <= k-1</code> 的节点 <code>z<sub>i</sub></code> 和 <code>z<sub>i+1</sub></code> 之间存在一条边。</p>\n",
    "\n",
    "<p>路径的距离定义为这条路径上所有边的权重总和。用 <code>distanceToLastNode(x)</code> 表示节点 <code>n</code> 和 <code>x</code> 之间路径的最短距离。<strong>受限路径</strong> 为满足 <code>distanceToLastNode(z<sub>i</sub>) > distanceToLastNode(z<sub>i+1</sub>)</code> 的一条路径，其中 <code>0 <= i <= k-1</code> 。</p>\n",
    "\n",
    "<p>返回从节点 <code>1</code> 出发到节点 <code>n</code> 的 <strong>受限路径数</strong> 。由于数字可能很大，请返回对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/03/07/restricted_paths_ex1.png\" style=\"width: 351px; height: 341px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。三条受限路径分别是：\n",
    "1) 1 --> 2 --> 5\n",
    "2) 1 --> 2 --> 3 --> 5\n",
    "3) 1 --> 3 --> 5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/03/07/restricted_paths_ex22.png\" style=\"width: 356px; height: 401px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。唯一一条受限路径是：1 --> 3 --> 7 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>n - 1 <= edges.length <= 4 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>edges[i].length == 3</code></li>\n",
    "\t<li><code>1 <= u<sub>i</sub>, v<sub>i</sub> <= n</code></li>\n",
    "\t<li><code>u<sub>i </sub>!= v<sub>i</sub></code></li>\n",
    "\t<li><code>1 <= weight<sub>i</sub> <= 10<sup>5</sup></code></li>\n",
    "\t<li>任意两个节点之间至多存在一条边</li>\n",
    "\t<li>任意两个节点之间至少存在一条路径</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-restricted-paths-from-first-to-last-node](https://leetcode.cn/problems/number-of-restricted-paths-from-first-to-last-node/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-restricted-paths-from-first-to-last-node](https://leetcode.cn/problems/number-of-restricted-paths-from-first-to-last-node/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]', '7\\n[[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dist = [2 * 10 ** 9] * (n + 1)\n",
    "        M = 10 ** 9 + 7\n",
    "        q = [(0, n)]\n",
    "        f = [0] * (n + 1)\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for a, b, c in edges:\n",
    "            g[a].append((b, c))\n",
    "            g[b].append((a, c))\n",
    "            \n",
    "        while q:\n",
    "            d, v = heappop(q)\n",
    "            if d >= dist[v]:\n",
    "                continue\n",
    "            dist[v] = d\n",
    "            for u, c in g[v]:\n",
    "                d2 = d + c\n",
    "                if d2 < dist[u]:\n",
    "                    heappush(q, (d2, u))\n",
    "    \n",
    "        idx = list(range(1, n + 1))\n",
    "        idx.sort(key=lambda i: dist[i])\n",
    "        f[n] = 1\n",
    "        for i in range(n):\n",
    "            node = idx[i]\n",
    "            for son, _ in g[node]:\n",
    "                if dist[son] > dist[node]:\n",
    "                    f[son] = (f[son] + f[node]) % M\n",
    "        return f[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dist = [2 * 10 ** 9] * (n + 1)\n",
    "        M = 10 ** 9 + 7\n",
    "        q = [(0, n)]\n",
    "        f = [0] * (n + 1)\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for a, b, c in edges:\n",
    "            g[a].append((b, c))\n",
    "            g[b].append((a, c))\n",
    "        vst = [0] * (n + 1)\n",
    "        while q:\n",
    "            d, v = heappop(q)\n",
    "            if vst[v]:\n",
    "                continue\n",
    "            vst[v] = 1\n",
    "            dist[v] = d\n",
    "            for u, c in g[v]:\n",
    "                d2 = d + c\n",
    "                if d2 < dist[u]:\n",
    "                    dist[u] = d2\n",
    "                    heappush(q, (d2, u))\n",
    "    \n",
    "        idx = list(range(1, n + 1))\n",
    "        idx.sort(key=lambda i: dist[i])\n",
    "        f[n] = 1\n",
    "        for i in range(n):\n",
    "            node = idx[i]\n",
    "            for son, _ in g[node]:\n",
    "                if dist[son] > dist[node]:\n",
    "                    f[son] = (f[son] + f[node]) % M\n",
    "        return f[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        def add(u,v,w):\n",
    "            nonlocal cnt\n",
    "            lines[cnt] = heads[u]\n",
    "            to[cnt] = v\n",
    "            weight[cnt] = w\n",
    "            heads[u] = cnt\n",
    "            cnt += 1\n",
    "        mod = 10**9+7\n",
    "        m = len(edges)*2\n",
    "        heads, lines, to, weight = [-1]*(n+1), [-1]*m, [-1]*m, [-1]*m\n",
    "        cnt = 0\n",
    "        for u,v,w in edges:\n",
    "            add(u,v,w)\n",
    "            add(v,u,w)\n",
    "        dis = [inf]*(n+1)\n",
    "        dis[n] = 0\n",
    "        vis = set()\n",
    "        q = [(0,n)]\n",
    "        while q:\n",
    "            d,u = heapq.heappop(q)\n",
    "            vis.add(u)\n",
    "            l = heads[u]\n",
    "            while l != -1:\n",
    "                v = to[l]\n",
    "                w = weight[l]\n",
    "                if v not in vis and dis[v] > d+w:\n",
    "                    dis[v] = d+w\n",
    "                    heapq.heappush(q, (dis[v], v))\n",
    "                l = lines[l]\n",
    "        idx = [x for x in range(n)]\n",
    "        idx.sort(reverse=True,key=lambda x:dis[x+1])\n",
    "        dp = [0]*(n+1)\n",
    "        dp[1] = 1\n",
    "        for i in range(n):\n",
    "            u = idx[i]+1\n",
    "            l = heads[u]\n",
    "            while l != -1:\n",
    "                v = to[l]\n",
    "                if dis[v] < dis[u]:\n",
    "                    dp[v] = (dp[u]+dp[v])%mod\n",
    "                l = lines[l]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a,b,v in edges:\n",
    "            g[a-1].append((b-1,v))\n",
    "            g[b-1].append((a-1,v))\n",
    "        dis = [inf] * n\n",
    "        dis[-1] = 0\n",
    "        \n",
    "        h = [(0,n-1)]\n",
    "        while h:\n",
    "            d,x = heapq.heappop(h)\n",
    "            for y,v in g[x]:\n",
    "                if dis[y] <= dis[x]+v: continue\n",
    "                dis[y] = dis[x] + v\n",
    "                heapq.heappush(h,(dis[y],y))\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        d = [0]*n\n",
    "        cnt = [0]*n\n",
    "        cnt[0] = 1\n",
    "        for a,b,v in edges:\n",
    "            a,b = a-1,b-1\n",
    "            if dis[a] == dis[b]: continue\n",
    "            if dis[a] < dis[b]: a,b = b,a\n",
    "            g[a].append(b)\n",
    "            d[b] += 1\n",
    "        q = [i for i in range(n) if d[i] == 0 and i]\n",
    "        while q:\n",
    "            x = q.pop()\n",
    "            for y in g[x]:\n",
    "                d[y] -= 1\n",
    "                if d[y] == 0 and y: q.append(y)\n",
    "        q = [0]\n",
    "        mod = 1000000007\n",
    "        while q:\n",
    "            x = q.pop()\n",
    "            for y in g[x]:\n",
    "                cnt[y] = (cnt[y] + cnt[x]) % mod\n",
    "                d[y] -= 1\n",
    "                if d[y] == 0: q.append(y)\n",
    "        return cnt[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "from functools import cache\n",
    "import math\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(dict)\n",
    "        for x, y, w in edges:\n",
    "            g[x][y] = w\n",
    "            g[y][x] = w\n",
    "\n",
    "        dist = [math.inf] * (n + 1)\n",
    "        dist[n] = 0\n",
    "        h = [(0, n)]\n",
    "        vis = set()\n",
    "        while h:\n",
    "            s, x = heapq.heappop(h)\n",
    "            vis.add(x)\n",
    "            for y in g[x].keys():\n",
    "                w = g[x][y]\n",
    "                if y not in vis and s + w < dist[y]:\n",
    "                    heapq.heappush(h, (s + w, y))\n",
    "                    dist[y] = s + w\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[n] = 1\n",
    "        for x in sorted(range(n + 1), key=lambda i: dist[i]):\n",
    "            if x == 1:\n",
    "                break\n",
    "            for y in g[x].keys():\n",
    "                if dist[y] > dist[x]:\n",
    "                    dp[y] = (dp[x] + dp[y]) % mod\n",
    "        return dp[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "MOD = 10**9+7\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dct = defaultdict(dict)\n",
    "        for i, j, w in edges:\n",
    "            dct[i-1][j-1] = w\n",
    "            dct[j-1][i-1] = w\n",
    "\n",
    "        # 使用倒序进行最短路搜寻\n",
    "        dis = [float('inf')]*n\n",
    "        cnt = [0]*n\n",
    "        cnt[n-1] = 1\n",
    "        dis[n-1] = 0\n",
    "        # 定义好初始值\n",
    "        stack = [[0, n-1]]\n",
    "        while stack:\n",
    "            cur_dis, cur = heapq.heappop(stack)\n",
    "            if dis[cur] < cur_dis:\n",
    "                continue\n",
    "            dis[cur] = cur_dis\n",
    "            for nex in dct[cur]:\n",
    "                # 如果到达下一个点更近，则更新值\n",
    "                if dis[nex] > dis[cur] + dct[cur][nex]:\n",
    "                    dis[nex] = dis[cur] + dct[cur][nex]\n",
    "                    heapq.heappush(stack, [dis[nex], nex])\n",
    "                # 可以形成有效的路径\n",
    "                if dis[cur] < dis[nex]:\n",
    "                    cnt[nex] += cnt[cur]\n",
    "                    cnt[nex] %= MOD\n",
    "        return cnt[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  \n",
    "    def countRestrictedPaths(self, n, edges):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type edges: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        g = defaultdict(list)\n",
    "        for a,b,w in edges:\n",
    "            g[a].append([b,w])\n",
    "            g[b].append([a,w])\n",
    "        pq = [(0,n)]\n",
    "        dist = [0x3f3f3f3f3f] * (n + 1)\n",
    "        dist[n] = 0\n",
    "        vis = [False] * (n + 1)\n",
    "        while pq:\n",
    "            d,cur = heapq.heappop(pq)\n",
    "            if vis[cur]:\n",
    "                continue\n",
    "            vis[cur] = True\n",
    "            for nei,wei in g[cur]:\n",
    "                if dist[nei] > wei + d:\n",
    "                    dist[nei] = wei + d\n",
    "                    heapq.heappush(pq,(dist[nei],nei))\n",
    "\n",
    "        g1 = defaultdict(list)\n",
    "        inc = [0] * (n + 1)\n",
    "        for a,b,w in edges:\n",
    "            if dist[a] > dist[b]:\n",
    "                g1[a].append(b)\n",
    "                inc[b] += 1\n",
    "            elif dist[b] > dist[a]:\n",
    "                g1[b].append(a)\n",
    "                inc[a] += 1\n",
    "    \n",
    "        q = deque()\n",
    "        for i in range(1,n + 1):\n",
    "            if inc[i] == 0:\n",
    "               q.append(i)\n",
    "        mod = pow(10,9) + 7\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 1\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for nei in g1[cur]:\n",
    "                inc[nei] -= 1\n",
    "                dp[nei] = (dp[cur] + dp[nei]) % mod\n",
    "                \n",
    "                if inc[nei] == 0:\n",
    "                    q.append(nei)\n",
    "   \n",
    "                   \n",
    "        return dp[n] % mod\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # build graph adj\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y, w in edges:\n",
    "            g[x - 1].append((y - 1, w))\n",
    "            g[y - 1].append((x - 1, w))\n",
    "        # dijkstra\n",
    "        dd = [inf] * n\n",
    "        dd[n - 1] = 0\n",
    "        pq = [(0, n - 1)]\n",
    "        while pq:\n",
    "            s, x = heappop(pq)\n",
    "            if s > dd[x]:\n",
    "                continue\n",
    "            for y, w in g[x]:\n",
    "                if s + w < dd[y]:\n",
    "                    dd[y] = s + w\n",
    "                    heappush(pq, (dd[y], y))\n",
    "        # dp\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [0] * n\n",
    "        dp[-1] = 1\n",
    "        ks = sorted(range(n), key=lambda i: (dd[i], -i))\n",
    "        for k in ks:\n",
    "            t = dd[k]\n",
    "            for y, _ in g[k]:\n",
    "                if dd[y] < t:\n",
    "                    dp[k] = (dp[k] + dp[y]) % MOD\n",
    "            if k == 0:\n",
    "                return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 1.先求所有的最短路径,从终点开始\n",
    "        g = defaultdict(list)\n",
    "        for x,y,w in edges:\n",
    "            g[x-1].append((y-1,w))\n",
    "            g[y-1].append((x-1,w))\n",
    "\n",
    "        dist = [float('inf')]*n\n",
    "        dist[n-1] = 0\n",
    "\n",
    "        MOD = 10**9+7\n",
    "\n",
    "        hq = []\n",
    "        hq.append((0,n-1))\n",
    "\n",
    "        cnt = [0]*n\n",
    "        cnt[n-1] = 1\n",
    "\n",
    "        while hq:\n",
    "            w1,x = heapq.heappop(hq)\n",
    "            if dist[x] < w1:\n",
    "                continue\n",
    "            for y,w2 in g[x]:\n",
    "                w = w1+w2\n",
    "                if w < dist[y]:\n",
    "                    dist[y] = w\n",
    "                    heapq.heappush(hq, (w,y))\n",
    "                if dist[x] < dist[y]:\n",
    "                    cnt[y] += cnt[x]\n",
    "                    cnt[y] %= MOD\n",
    "        print(cnt,dist)\n",
    "        return cnt[0]\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        # 2.dfs检查所有路径"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y, w in edges:\n",
    "            g[x-1].append([y - 1, w])\n",
    "            g[y-1].append([x - 1, w])\n",
    "        \n",
    "        dist = [inf] * n\n",
    "        heap = [[0, n-1]]\n",
    "\n",
    "        while heap:\n",
    "            d, idx = heapq.heappop(heap)\n",
    "            if dist[idx] <= d:\n",
    "                continue\n",
    "            dist[idx] = d\n",
    "\n",
    "            for y, w in g[idx]:\n",
    "                if w + d < dist[y]:\n",
    "                    heapq.heappush(heap, [d + w, y])\n",
    "        \n",
    "        f = [0] * n\n",
    "        f[n-1] = 1\n",
    "        order = sorted(list(range(n)), key=lambda x: dist[x])\n",
    "\n",
    "        for p in order:\n",
    "            for nxt, _ in g[p]:\n",
    "                if dist[nxt] > dist[p]:\n",
    "                    f[nxt] = (f[nxt] + f[p]) % MOD\n",
    "            if p == 0:\n",
    "                break\n",
    "        \n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y, w in edges:\n",
    "            g[x-1].append([y - 1, w])\n",
    "            g[y-1].append([x - 1, w])\n",
    "        \n",
    "        dist = [inf] * n\n",
    "        heap = [[0, n-1]]\n",
    "        visit = set()\n",
    "\n",
    "        while heap:\n",
    "            d, idx = heapq.heappop(heap)\n",
    "            if idx in visit:\n",
    "                continue\n",
    "            visit.add(idx)\n",
    "            dist[idx] = d\n",
    "\n",
    "            for y, w in g[idx]:\n",
    "                if w + d < dist[y]:\n",
    "                    heapq.heappush(heap, [d + w, y])\n",
    "        \n",
    "        f = [0] * n\n",
    "        f[n-1] = 1\n",
    "        order = sorted(list(range(n)), key=lambda x: dist[x])\n",
    "\n",
    "        for p in order:\n",
    "            for nxt, _ in g[p]:\n",
    "                if dist[nxt] > dist[p]:\n",
    "                    f[nxt] = (f[nxt] + f[p]) % MOD\n",
    "            if p == 0:\n",
    "                break\n",
    "        \n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        edge = defaultdict(dict)                #既是邻接矩阵，又是邻接表\n",
    "        for x,y,weight in edges:\n",
    "            edge[x][y] = weight\n",
    "            edge[y][x] = weight\n",
    "        #n为源点，dijkstra单源最短路径,n到各点的最短距离，就是各点到n的最短距离\n",
    "        dist = [float('inf') for _ in range(n + 1)]\n",
    "        dist[n] = 0\n",
    "        visited = set()\n",
    "        minHeap = [(0, n)]\n",
    "        while minHeap:\n",
    "            cloestDist, cloestNode = heapq.heappop(minHeap) #距离源节点最近的结点\n",
    "            if cloestNode in visited:           #已经在选中的区域里了，就不要再选了\n",
    "                continue\n",
    "            visited.add(cloestNode)             #未选择的点中，这是最小的。正式加入区域\n",
    "            for nxt in edge[cloestNode].keys():      #更新与它相连接的点\n",
    "                if dist[cloestNode] + edge[cloestNode][nxt] < dist[nxt]:\n",
    "                    dist[nxt] = dist[cloestNode] + edge[cloestNode][nxt]\n",
    "                    heapq.heappush(minHeap, (dist[nxt], nxt))              #有更小的了，就进minHeap\n",
    "        #动态规划 dp  更多的是一种贪心！！！！！！！！！\n",
    "        dp = [0 for _ in range(n + 1)]\n",
    "        dp[n] = 1\n",
    "        a = [node for node in range(1, n + 1)]\n",
    "        a.sort(key = lambda x: dist[x])\n",
    "\n",
    "        for node in a:\n",
    "            for nxt in edge[node].keys():\n",
    "                if dist[node] > dist[nxt]:\n",
    "                    dp[node] += dp[nxt]\n",
    "\n",
    "            if node == 1:   #a中右侧的点，距离都比1的远了，1的最短路径不可能经过他们到达n\n",
    "                break\n",
    "        \n",
    "        return dp[1] % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        edge = defaultdict(dict)                #既是邻接矩阵，又是邻接表\n",
    "        for x,y,weight in edges:\n",
    "            edge[x][y] = weight\n",
    "            edge[y][x] = weight\n",
    "        #n为源点，dijkstra单源最短路径,n到各点的最短距离，就是各点到n的最短距离\n",
    "        dist = [float('inf') for _ in range(n + 1)]\n",
    "        dist[n] = 0\n",
    "        visited = set()\n",
    "        minHeap = [(0, n)]\n",
    "        while minHeap:\n",
    "            cloestDist, cloestNode = heapq.heappop(minHeap) #距离源节点最近的结点\n",
    "            if cloestNode in visited:           #已经在选中的区域里了，就不要再选了\n",
    "                continue\n",
    "            visited.add(cloestNode)             #未选择的点中，这是最小的。正式加入区域\n",
    "            for nxt in edge[cloestNode].keys():      #更新与它相连接的点\n",
    "                if dist[cloestNode] + edge[cloestNode][nxt] < dist[nxt]:\n",
    "                    dist[nxt] = dist[cloestNode] + edge[cloestNode][nxt]\n",
    "                    heapq.heappush(minHeap, (dist[nxt], nxt))              #有更小的了，就进minHeap\n",
    "        #动态规划 dp  更多的是一种贪心！！！！！！！！！\n",
    "        dp = [0 for _ in range(n + 1)]\n",
    "        dp[n] = 1\n",
    "        a = [node for node in range(1, n + 1)]\n",
    "        a.sort(key = lambda x: dist[x])\n",
    "\n",
    "        for node in a:\n",
    "            for nxt in edge[node].keys():\n",
    "                if dist[node] > dist[nxt]:\n",
    "                    dp[node] += dp[nxt]\n",
    "\n",
    "            if node == 1:   #a中右侧的点，距离都比1的远了，1的最短路径不可能经过他们到达n\n",
    "                break\n",
    "        \n",
    "        return dp[1] % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        min_cost_dict = {n: 0}\n",
    "        nxt_dict = defaultdict(list)\n",
    "        cost_dict = {}\n",
    "        for x, y, cost in edges:\n",
    "            nxt_dict[x].append(y)\n",
    "            nxt_dict[y].append(x)\n",
    "            cost_dict[(x, y)] = cost\n",
    "            cost_dict[(y, x)] = cost\n",
    "        lst = [[0, n]]\n",
    "        used = set()\n",
    "        while lst:\n",
    "            cur_cost, cur_id = heappop(lst)\n",
    "            if cur_id in used:\n",
    "                continue\n",
    "            used.add(cur_id)\n",
    "            for nxt_id in nxt_dict[cur_id]:\n",
    "                nxt_cost = cur_cost + cost_dict[(cur_id, nxt_id)]\n",
    "                if nxt_id not in min_cost_dict or min_cost_dict[nxt_id] > nxt_cost:\n",
    "                    min_cost_dict[nxt_id] = nxt_cost\n",
    "                    heappush(lst, [nxt_cost, nxt_id])\n",
    "        count_dict = defaultdict(int)\n",
    "        count_dict[1] = 1\n",
    "        lst = [[-min_cost_dict[1], 1]]\n",
    "        used = {1}\n",
    "        while lst:\n",
    "            cur_cost, cur_id = heappop(lst)\n",
    "            if cur_id == n:\n",
    "                continue\n",
    "            cur_cost = -cur_cost\n",
    "            cur_count = count_dict[cur_id]\n",
    "            for nxt_id in nxt_dict[cur_id]:\n",
    "                nxt_cost = min_cost_dict[nxt_id]\n",
    "                if nxt_cost < cur_cost:\n",
    "                    count_dict[nxt_id] += cur_count\n",
    "                    if nxt_id not in used:\n",
    "                        used.add(nxt_id)\n",
    "                        heappush(lst, [-min_cost_dict[nxt_id], nxt_id])\n",
    "        return count_dict[n] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n+1)]\n",
    "        for a, b, c in edges:\n",
    "            graph[a].append([b, c])\n",
    "            graph[b].append([a, c])\n",
    "        \n",
    "        q = [(0, n)]\n",
    "        seen = [0]*(n+1)\n",
    "        dist = [0]*(n+1)\n",
    "        while q:\n",
    "            dist_node, node = heapq.heappop(q)\n",
    "            if seen[node]:\n",
    "                continue\n",
    "            seen[node] = 1\n",
    "            dist[node] = dist_node\n",
    "            for neighbor, nx_dist in graph[node]:\n",
    "                heapq.heappush(q, (dist_node+nx_dist, neighbor))\n",
    "        nodes = list(range(1, n+1))\n",
    "        nodes.sort(key=lambda x:dist[x])\n",
    "        dp = [0]*(n+1)\n",
    "        dp[-1] = 1\n",
    "        for node in nodes:\n",
    "            for neighbor, _ in graph[node]:\n",
    "                if dist[neighbor] > dist[node]:\n",
    "                    dp[neighbor] += dp[node]\n",
    "        return dp[1]%(10**9+7)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        import heapq\n",
    "        edge_length = defaultdict(dict)\n",
    "        for edge in edges:\n",
    "            edge_length[edge[0]][edge[1]] = edge[2]\n",
    "            edge_length[edge[1]][edge[0]] = edge[2]\n",
    "        distance = [sys.maxsize] * (n + 1)\n",
    "        distance[n] = 0\n",
    "        seen = set()\n",
    "        queue = [(0, n)]\n",
    "\n",
    "        while queue:\n",
    "            _, src = heapq.heappop(queue)\n",
    "            if src not in seen:\n",
    "                seen.add(src)\n",
    "                for dest, cost in edge_length.get(src).items():\n",
    "                    distance[dest] = min(distance[dest], distance[src] + cost)\n",
    "                    heapq.heappush(queue, (distance[dest], dest))\n",
    "\n",
    "        dist_vertex = [(v, i) for i, v in enumerate(distance) if i > 0]\n",
    "        dist_vertex.sort()\n",
    "\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[n] = 1\n",
    "        for _, src in dist_vertex:\n",
    "            for dst, _ in edge_length.get(src).items():\n",
    "                if distance[src] < distance[dst]:\n",
    "                    dp[dst] += dp[src]\n",
    "\n",
    "        return dp[1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        import heapq\n",
    "        edge_length = defaultdict(dict)\n",
    "        for edge in edges:\n",
    "            edge_length[edge[0]][edge[1]] = edge[2]\n",
    "            edge_length[edge[1]][edge[0]] = edge[2]\n",
    "        distance = [sys.maxsize] * (n + 1)\n",
    "        distance[n] = 0\n",
    "        seen = set()\n",
    "        queue = [(0, n)]\n",
    "\n",
    "        while queue:\n",
    "            _, src = heapq.heappop(queue)\n",
    "            if src not in seen:\n",
    "                seen.add(src)\n",
    "                for dest, cost in edge_length.get(src).items():\n",
    "                    distance[dest] = min(distance[dest], distance[src] + cost)\n",
    "                    heapq.heappush(queue, (distance[dest], dest))\n",
    "\n",
    "        dist_vertex = [(v, i) for i, v in enumerate(distance) if i > 0]\n",
    "        dist_vertex.sort()\n",
    "\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[n] = 1\n",
    "        for _, src in dist_vertex:\n",
    "            for dst, _ in edge_length.get(src).items():\n",
    "                if distance[src] < distance[dst]:\n",
    "                    dp[dst] += dp[src]\n",
    "\n",
    "        return dp[1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "      table = defaultdict(list)\n",
    "\n",
    "      for x, y, w in edges:\n",
    "        table[x].append((y, w))\n",
    "        table[y].append((x, w))\n",
    "\n",
    "      def dijkstra():\n",
    "        INF = float(\"inf\")\n",
    "        dist = [INF] * (n + 1)\n",
    "        dist[n] = 0\n",
    "        visited = set()\n",
    "        \n",
    "        heap = [(d, i) for i, d in enumerate(dist) if x != 0]\n",
    "        heapify(heap)\n",
    "\n",
    "        while heap:\n",
    "          d, i = heappop(heap)\n",
    "          if i in visited:\n",
    "            continue\n",
    "          visited.add(i)\n",
    "          dist[i] = d\n",
    "          for j, w in table[i]:\n",
    "            heappush(heap, (d + w, j))\n",
    "\n",
    "        return dist\n",
    "\n",
    "      dist = dijkstra()\n",
    "\n",
    "      dp = [0] * (n + 1)\n",
    "      dp[n] = 1\n",
    "\n",
    "      pairs = [(y, x) for x, y in enumerate(dist) if x != 0]\n",
    "      pairs.sort()\n",
    "      \n",
    "      for d, i in pairs:\n",
    "        for j, _ in table[i]:\n",
    "          if d > dist[j]:\n",
    "            dp[i] += dp[j]\n",
    "        if i == 1:\n",
    "          break\n",
    "\n",
    "      return dp[1] % (int(1e9) + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        def relax(u: int, v: int, w: int) -> None:\n",
    "            if dist[v] > (d := dist[u] + w):\n",
    "                dist[v] = d \n",
    "                heapq.heappush(pq, (d, v))\n",
    "\n",
    "        # 1. O(V+E) build adjacency list of undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            g[u-1].append((v-1, w))\n",
    "            g[v-1].append((u-1, w))\n",
    "\n",
    "        # 2. O((V+E)logV) run heap-optimized Dijkastra's algorithm\n",
    "        start_node = n-1 \n",
    "        dist = [math.inf] * n  \n",
    "        dist[start_node] = 0 \n",
    "        pq = [(0, start_node)]  # min-heap\n",
    "        while pq:\n",
    "            d, u = heapq.heappop(pq)\n",
    "            if d > dist[u]:    \n",
    "                continue\n",
    "       \n",
    "            for v, w in g[u]:\n",
    "                relax(u, v, w)\n",
    "\n",
    "        # 3. DP\n",
    "\n",
    "        # sort vertices by shortest distance ascendingly\n",
    "        vertices = sorted(list(range(n)), key=lambda x: dist[x])\n",
    "\n",
    "        dp = [0] * n \n",
    "        dp[n-1] = 1\n",
    "        for i in vertices:\n",
    "            for j, _ in g[i]:\n",
    "                if dist[i] > dist[j]:\n",
    "                    dp[i] += dp[j]\n",
    "\n",
    "        return dp[0] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b, w in edges:\n",
    "            g[a-1].append((b-1, w))\n",
    "            g[b-1].append((a-1, w))\n",
    "        dis = [inf] * n\n",
    "        dis[n-1] = 0\n",
    "        vis = [False] * n\n",
    "        q = [(0, n-1)]\n",
    "        while q:\n",
    "            s, x = heappop(q)\n",
    "            if dis[x] < s or vis[x]: continue\n",
    "            vis[x] = True\n",
    "            for y, w in g[x]:\n",
    "                d = dis[x] + w \n",
    "                if d < dis[y]:\n",
    "                    dis[y] = d \n",
    "                    heappush(q, (d, y))\n",
    "                    \n",
    "        # print(dis)\n",
    "        dp = [0] * n\n",
    "        dp[n-1] = 1\n",
    "        a = sorted(list(range(n)), key=lambda x:dis[x])\n",
    "        for x in a:\n",
    "            for y,_ in g[x]:\n",
    "                if dis[x] > dis[y]:\n",
    "                    dp[x] += dp[y]\n",
    "            if x == 0:\n",
    "                break\n",
    "        return dp[0] % (10 ** 9 + 7)\n",
    "         \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        def Dijkstra(start_node: int, n: int, g: List[List[int]]) -> List[int]:\n",
    "            def relax(u: int, v: int, w: int) -> None:\n",
    "                if dist[v] > (d := dist[u] + w):\n",
    "                    dist[v] = d \n",
    "                    heapq.heappush(pq, (d, v))\n",
    "            \n",
    "            dist = [math.inf] * n  \n",
    "            dist[start_node] = 0 \n",
    "            pq = [(0, start_node)]  # min-heap\n",
    "            while pq:\n",
    "                d, u = heapq.heappop(pq)\n",
    "                if d > dist[u]:    \n",
    "                    continue\n",
    "        \n",
    "                for v, w in g[u]:\n",
    "                    relax(u, v, w)\n",
    "            return dist\n",
    "\n",
    "        # 1. O(V+E) build adjacency list of undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            g[u-1].append((v-1, w))\n",
    "            g[v-1].append((u-1, w))\n",
    "\n",
    "        # 2. O((V+E)logV) run heap-optimized Dijkstra's algorithm\n",
    "        dist = Dijkstra(n-1, n, g)\n",
    "\n",
    "        # 3. O(V+E) DP\n",
    "        dp = [0] * n \n",
    "        dp[n-1] = 1\n",
    "\n",
    "        # O(V) sort vertices by shortest distance ascendingly\n",
    "        vertices = sorted(list(range(n)), key=lambda x: dist[x])\n",
    "        \n",
    "        # start from nearest vertex from vertex n \n",
    "        for i in vertices:\n",
    "            for j, _ in g[i]:\n",
    "                if dist[i] > dist[j]:\n",
    "                    dp[i] += dp[j]\n",
    "\n",
    "        return dp[0] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for f, t, w in edges:\n",
    "            graph[f].append((t, w))\n",
    "            graph[t].append((f, w))\n",
    "\n",
    "        distance = [float('inf')] * (n + 1)\n",
    "        distance[n] = 0\n",
    "        que, visited = [[0, n]], set()\n",
    "        while que:\n",
    "            _, src = heapq.heappop(que)\n",
    "            if src not in visited:\n",
    "                visited.add(src)\n",
    "                for nxt, w in graph[src]:\n",
    "                    distance[nxt] = min(distance[nxt], distance[src] + w)\n",
    "                    heapq.heappush(que, [distance[nxt], nxt])\n",
    "\n",
    "        sorted_distance = sorted((w, idx) for idx, w in enumerate(distance[1:], 1))\n",
    "        # print(sorted_distance)\n",
    "\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[n] = 1\n",
    "        for _, src in sorted_distance:\n",
    "            for nxt, _ in graph[src]:\n",
    "                if distance[src] < distance[nxt]:\n",
    "                    dp[nxt] += dp[src]\n",
    "        return dp[1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for u, v, w in edges:\n",
    "            u -= 1\n",
    "            v -= 1\n",
    "            g[u].append([v, w])\n",
    "            g[v].append([u, w])\n",
    "            deg[u] += 1\n",
    "            deg[v] += 1\n",
    "\n",
    "        pq = []\n",
    "        heappush(pq, [0, n-1])\n",
    "        dist = dict()\n",
    "        dist[n-1] = 0\n",
    "        while pq:\n",
    "            d, x = heappop(pq)\n",
    "            for y, w in g[x]:\n",
    "                if y not in dist or dist[y] > d + w:\n",
    "                    dist[y] = d+w\n",
    "                    heappush(pq, [d+w, y])\n",
    "\n",
    "        dp = [0] * n\n",
    "        dp[0] = 1\n",
    "        pq = []\n",
    "        heappush(pq, [-dist[0], 0])\n",
    "        vis = set()\n",
    "\n",
    "        while pq:\n",
    "            d, x = heappop(pq)\n",
    "            if x in vis:\n",
    "                continue\n",
    "            vis.add(x)\n",
    "            for y, _ in g[x]:\n",
    "                if dist[y] < dist[x]:\n",
    "                    dp[y] += dp[x]\n",
    "                    heappush(pq, [-dist[y], y])\n",
    "        return dp[-1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        neis = collections.defaultdict(list) # 改dict没有提速\n",
    "        for x, y, c in edges:\n",
    "            neis[x].append((y, c))\n",
    "            neis[y].append((x, c))\n",
    "        pq = []\n",
    "        heapq.heappush(pq, (0, n))  # cost(priority) location\n",
    "        costs = {n: 0}\n",
    "        while pq:\n",
    "            curCost, cur = heapq.heappop(pq)\n",
    "            for nei, cost in neis[cur]:\n",
    "                neiCost = curCost + cost\n",
    "                if nei not in costs or neiCost < costs[nei]:\n",
    "                    costs[nei] = neiCost\n",
    "                    heapq.heappush(pq, (neiCost, nei))\n",
    "\n",
    "        mem = {n:1}\n",
    "        def dfs(root):\n",
    "            if root in mem:\n",
    "                return mem[root]\n",
    "\n",
    "            mem[root] = 0\n",
    "            for v, _ in neis[root]:\n",
    "                if costs[root] > costs[v]:\n",
    "                    mem[root] += dfs(v)\n",
    "                    mem[root] %= mod\n",
    "\n",
    "            return mem[root]\n",
    "\n",
    "        return dfs(1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        neis = collections.defaultdict(list) # 改dict没有提速\n",
    "        for x, y, c in edges:\n",
    "            neis[x].append((y, c))\n",
    "            neis[y].append((x, c))\n",
    "        pq = []\n",
    "        heapq.heappush(pq, (0, n))  # cost(priority) location\n",
    "        costs = {n: 0}\n",
    "        while pq:\n",
    "            curCost, cur = heapq.heappop(pq)\n",
    "            for nei, cost in neis[cur]:\n",
    "                neiCost = curCost + cost\n",
    "                if nei not in costs or neiCost < costs[nei]:\n",
    "                    costs[nei] = neiCost\n",
    "                    heapq.heappush(pq, (neiCost, nei))\n",
    "\n",
    "        mem = {n:1}\n",
    "        def dfs(root):\n",
    "            if root in mem:\n",
    "                return mem[root]\n",
    "\n",
    "            mem[root] = 0\n",
    "            for v, _ in neis[root]:\n",
    "                if costs[root] > costs[v]:\n",
    "                    mem[root] += dfs(v)\n",
    "                    mem[root] %= mod\n",
    "\n",
    "            return mem[root]\n",
    "\n",
    "        return dfs(1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,w in edges:\n",
    "            graph[u-1].append((v-1,w))\n",
    "            graph[v-1].append((u-1,w))\n",
    "        dist = [float('inf')]*n\n",
    "        dist[-1] = 0\n",
    "        queue = [(0,n-1)]\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN, nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN], nextN))\n",
    "\n",
    "        rec = [-1]*n\n",
    "        rec[n-1] = 1\n",
    "        MOD = 10**9+7\n",
    "        def dfs(node):\n",
    "            if not rec[node]==-1:\n",
    "                return rec[node]\n",
    "            total = 0\n",
    "            for nextN,nextD in graph[node]:\n",
    "                if dist[node] > dist[nextN]:\n",
    "                    total += dfs(nextN)\n",
    "            rec[node] = total%MOD\n",
    "            return rec[node]\n",
    "\n",
    "        dfs(0)\n",
    "        return rec[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for a, b, w in edges:\n",
    "            g[a].append((b, w))\n",
    "            g[b].append((a, w))\n",
    "        \n",
    "        dist = [inf] * (n + 1)\n",
    "        q = []\n",
    "        dist[n] = 0\n",
    "        heappush(q, (0, n))\n",
    "        while q:\n",
    "            d, x = heappop(q)\n",
    "            if d > dist[x]: continue\n",
    "            for y, w in g[x]:\n",
    "                nd = d + w\n",
    "                if nd < dist[y]:\n",
    "                    dist[y] = nd\n",
    "                    heappush(q, (nd, y))\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for y, _ in g[i]:\n",
    "                if dist[y] > dist[i]:\n",
    "                    res += dfs(y)\n",
    "                    #res %= mod\n",
    "            return res % mod\n",
    "        return dfs(n)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for a, b, w in edges:\n",
    "            g[a].append((b, w))\n",
    "            g[b].append((a, w))\n",
    "        \n",
    "        dist = [inf] * (n + 1)\n",
    "        q = []\n",
    "        dist[n] = 0\n",
    "        heappush(q, (0, n))\n",
    "        while q:\n",
    "            d, x = heappop(q)\n",
    "            if d > dist[x]: continue\n",
    "            for y, w in g[x]:\n",
    "                nd = d + w\n",
    "                if nd < dist[y]:\n",
    "                    dist[y] = nd\n",
    "                    heappush(q, (nd, y))\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for y, _ in g[i]:\n",
    "                if dist[y] > dist[i]:\n",
    "                    res += dfs(y)\n",
    "                    #res %= mod\n",
    "            return res % mod\n",
    "        return dfs(n)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for a, b, w in edges:\n",
    "            g[a].append((b, w))\n",
    "            g[b].append((a, w))\n",
    "        \n",
    "        dist = [inf] * (n + 1)\n",
    "        q = []\n",
    "        dist[n] = 0\n",
    "        heappush(q, (0, n))\n",
    "        while q:\n",
    "            d, x = heappop(q)\n",
    "            if d > dist[x]: continue\n",
    "            for y, w in g[x]:\n",
    "                nd = d + w\n",
    "                if nd < dist[y]:\n",
    "                    dist[y] = nd\n",
    "                    heappush(q, (nd, y))\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for y, _ in g[i]:\n",
    "                if dist[y] > dist[i]:\n",
    "                    res += dfs(y)\n",
    "                    res %= mod\n",
    "            return res\n",
    "        return dfs(n)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        pq = PriorityQueue()\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for u,v,w in edges:\n",
    "            g[u].append((v,w))\n",
    "            g[v].append((u,w))\n",
    "        dis = [inf] * (n + 1)\n",
    "        dis[n] = 0\n",
    "        pq.put((0,n))\n",
    "        while not pq.empty():\n",
    "            d,u = pq.get()\n",
    "            for v,w in g[u]:\n",
    "                if dis[v] > d + w:\n",
    "                    dis[v] = d + w\n",
    "                    pq.put((dis[v], v))\n",
    "        mod = int(1e9+7)\n",
    "        @cache\n",
    "        def f(u):\n",
    "            if u == n:\n",
    "                return 1\n",
    "            r = 0\n",
    "            for v,_ in g[u]:\n",
    "                if dis[v] < dis[u]:\n",
    "                    r = (r + f(v)) % mod\n",
    "            return r \n",
    "        return f(1)\n",
    "\n",
    "\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        pq = PriorityQueue()\n",
    "        g=[[] for _ in range(n+1)]\n",
    "        for u,v,w in edges:\n",
    "            g[u].append((v,w))\n",
    "            g[v].append((u,w))\n",
    "        dis=[inf]*(n+1)\n",
    "        dis[n]=0\n",
    "        pq.put((0,n))\n",
    "        while not pq.empty():\n",
    "            d,u=pq.get()\n",
    "            for v,w in g[u]:\n",
    "                if dis[v]>d+w:\n",
    "                    dis[v]=d+w\n",
    "                    pq.put((dis[v],v))\n",
    "        mod=int(1e9+7)\n",
    "        @cache\n",
    "        def f(u):\n",
    "            if u==n:\n",
    "                return 1\n",
    "            r=0\n",
    "            for v,_ in g[u]:\n",
    "                if dis[v]<dis[u]:\n",
    "                    r=(r+f(v))%mod\n",
    "            return r\n",
    "        return f(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for a, b, w in edges:\n",
    "            g[a].append((b, w))\n",
    "            g[b].append((a, w))\n",
    "        \n",
    "        dist = [inf] * (n + 1)\n",
    "        q = []\n",
    "        dist[n] = 0\n",
    "        heappush(q, (0, n))\n",
    "        while q:\n",
    "            d, x = heappop(q)\n",
    "            if d > dist[x]: continue\n",
    "            for y, w in g[x]:\n",
    "                nd = d + w\n",
    "                if nd < dist[y]:\n",
    "                    dist[y] = nd\n",
    "                    heappush(q, (nd, y))\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for y, _ in g[i]:\n",
    "                if dist[y] > dist[i]:\n",
    "                    res += dfs(y)\n",
    "                    res %= mod\n",
    "            return res\n",
    "        return dfs(n)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        pq = PriorityQueue()\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for u,v,w in edges:\n",
    "            g[u].append((v,w))\n",
    "            g[v].append((u,w))\n",
    "        # dis[i] 表示 n 到 i 节点的最短距离\n",
    "        dis = [inf] * (n + 1)\n",
    "        dis[n] = 0\n",
    "        pq.put((0,n))\n",
    "        while not pq.empty():\n",
    "            d,u = pq.get()\n",
    "            for v,w in g[u]:\n",
    "                if dis[v] > d + w:\n",
    "                    dis[v] = d + w\n",
    "                    pq.put((dis[v], v))\n",
    "        mod = int(1e9+7)\n",
    "        # u 节点到 n 节点的受限路径数目\n",
    "        @cache\n",
    "        def f(u):\n",
    "            if u == n:\n",
    "                return 1\n",
    "            r = 0\n",
    "            for v,_ in g[u]:\n",
    "                if dis[v] < dis[u]:\n",
    "                    r = (r + f(v)) % mod\n",
    "            return r \n",
    "        return f(1)\n",
    "\n",
    "\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        edges=[[x-1,y-1,w] for x,y,w in edges]\n",
    "        m=10**10\n",
    "        dist=[m]*n\n",
    "        dist[n-1]=0\n",
    "        adj=defaultdict(list)\n",
    "        for x,y,d in edges:\n",
    "            adj[x].append([d,y])\n",
    "            adj[y].append([d,x])\n",
    "        h=[]\n",
    "        heapq.heappush(h,[0,n-1])\n",
    "        while h:\n",
    "            d,x=heapq.heappop(h)\n",
    "            for cost,y in adj[x]:\n",
    "                if dist[y]<=dist[x]+cost:\n",
    "                    continue\n",
    "                else:\n",
    "                    dist[y]=dist[x]+cost\n",
    "                    heapq.heappush(h,[dist[y],y])\n",
    "        points=[[dist[i],i] for i in range (0,n)]\n",
    "\n",
    "        points.sort()\n",
    "        dp=defaultdict(int)\n",
    "        dp[n-1]=1\n",
    "        for _,point in points:\n",
    "            for _,v in adj[point]:\n",
    "                if dist[v]>dist[point]:\n",
    "                    dp[v]=dp[v]+dp[point]\n",
    "            \n",
    "            if point==0:\n",
    "                break\n",
    "        \n",
    "        return dp[0]%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a, b, w in edges:\n",
    "            g[a].append((b, w))\n",
    "            g[b].append((a, w))        \n",
    "        \n",
    "        dtl = [inf] * (n + 1)\n",
    "        dtl[n] = 0\n",
    "        hp = [(0, n)]\n",
    "        while hp:\n",
    "            cur, u = heappop(hp)\n",
    "            if cur > dtl[u]:\n",
    "                continue\n",
    "            for v, w in g[u]:\n",
    "                if cur + w < dtl[v]:\n",
    "                    dtl[v] = cur + w\n",
    "                    heappush(hp, (cur + w, v))\n",
    "        # print(dtl)\n",
    "        @cache\n",
    "        def dfs(u):\n",
    "            if u == n:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for v, _ in g[u]:\n",
    "                if dtl[u] > dtl[v]:\n",
    "                    ans = (ans + dfs(v)) % MOD\n",
    "            return ans    \n",
    "        return dfs(1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        dct = defaultdict(dict)\n",
    "        for u, v, w in edges:\n",
    "            dct[u][v] = w\n",
    "            dct[v][u] = w\n",
    "\n",
    "        # 倒序寻找最近距离\n",
    "        dis = [float(\"inf\")] * (n + 1)\n",
    "        stack = [[0, n]]\n",
    "        while stack:\n",
    "            cur, i = heapq.heappop(stack)\n",
    "            if dis[i] <= cur:\n",
    "                continue\n",
    "            dis[i] = cur\n",
    "            for j in dct[i]:\n",
    "                heapq.heappush(stack, [cur + dct[i][j], j])\n",
    "\n",
    "        # 按照最近距离建图\n",
    "        rise = defaultdict(list)\n",
    "        for u, v, _ in edges:\n",
    "            if dis[u] < dis[v]:\n",
    "                rise[u].append(v)\n",
    "            if dis[v] < dis[u]:\n",
    "                rise[v].append(u)\n",
    "\n",
    "        # 记忆化搜索\n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            if x == 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for y in rise[x]:\n",
    "                res += dfs(y)\n",
    "            res %= MOD\n",
    "            return res\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        m = len(edges)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        for a, b, w in edges:\n",
    "            g[a].append((b, w))\n",
    "            g[b].append((a, w))\n",
    "\n",
    "        q = [(0, n)]\n",
    "\n",
    "        dists = [inf] * (n + 1)\n",
    "\n",
    "        while q:\n",
    "            d, x = heappop(q)\n",
    "            \n",
    "            if d < dists[x]:\n",
    "                dists[x] = d\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "            for y, w in g[x]:\n",
    "                nd = d + w\n",
    "\n",
    "                if nd < dists[y]:\n",
    "                    heappush(q, (nd, y))\n",
    "\n",
    "        @cache\n",
    "        def dp(x):\n",
    "            if x == n:\n",
    "                return 1\n",
    "\n",
    "            ret = 0\n",
    "\n",
    "            for y, w in g[x]:\n",
    "                if dists[y] < dists[x]:\n",
    "                    ret += dp(y)\n",
    "                    ret %= MOD\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dp(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for a, b, w in edges:\n",
    "            g[a].append((b, w))\n",
    "            g[b].append((a, w))\n",
    "        \n",
    "        dist = [inf] * (n + 1)\n",
    "        q = []\n",
    "        dist[n] = 0\n",
    "        heappush(q, (0, n))\n",
    "        while q:\n",
    "            d, x = heappop(q)\n",
    "            #if d > dist[x]: continue\n",
    "            for y, w in g[x]:\n",
    "                nd = d + w\n",
    "                if nd < dist[y]:\n",
    "                    dist[y] = nd\n",
    "                    heappush(q, (nd, y))\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for y, _ in g[i]:\n",
    "                if dist[y] > dist[i]:\n",
    "                    res += dfs(y)\n",
    "                    #res %= mod\n",
    "            return res % mod\n",
    "        return dfs(n)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(dict)\n",
    "        for a, b, w in edges:\n",
    "            g[a - 1][b - 1] = g[b - 1][a - 1] = w\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # dist[i]表示i到n的最短距离\n",
    "        dist = [float('inf')] * (n - 1) + [0]\n",
    "        h = [(0, n - 1)]\n",
    "        while h:\n",
    "            w_a, a = heappop(h)\n",
    "            if w_a != dist[a]:\n",
    "                continue\n",
    "            for b, w_b in g[a].items():\n",
    "                if (w := w_a + w_b) < dist[b]:\n",
    "                    heappush(h, (w, b))\n",
    "                    dist[b] = w\n",
    "\n",
    "        d = {n - 1: 1}\n",
    "        def DFS(a):\n",
    "            if a in d:\n",
    "                return d[a]\n",
    "            d[a] = 0\n",
    "            for b, w in g[a].items():\n",
    "                if dist[a] > dist[b]:\n",
    "                    d[a] += DFS(b)\n",
    "                    d[a] %= MOD\n",
    "            return d[a]\n",
    "        # print(dist)\n",
    "        # print(d)\n",
    "        return DFS(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        g = defaultdict(dict)\n",
    "        for u, v, w in edges:\n",
    "            g[u][v] = w\n",
    "            g[v][u] = w\n",
    "        def dijkstra(edges: List[List[int]], src: int) -> int:\n",
    "            hpq = [[0, src]]\n",
    "            dist = [-1] * (n+1)\n",
    "            while hpq:\n",
    "                d, u = heapq.heappop(hpq)\n",
    "                if dist[u] != -1: continue\n",
    "                dist[u] = d\n",
    "                for v, w in g[u].items():\n",
    "                    heapq.heappush(hpq, [d + w , v])\n",
    "            return dist\n",
    "        \n",
    "        dist = dijkstra(edges, n)\n",
    "\n",
    "        @cache\n",
    "        def dfs(u):\n",
    "            if u == 1: return 1\n",
    "            res = 0\n",
    "            for nxt in g[u]:\n",
    "                if dist[nxt] > dist[u]:\n",
    "                    res += dfs(nxt)\n",
    "                    res %= mod\n",
    "            return res\n",
    "        return dfs(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dijkstra(graph, cost, start):\n",
    "    n = len(graph)\n",
    "    dis = [inf] * n\n",
    "    dis[start] = 0\n",
    "    q = [(0, start)]\n",
    "\n",
    "    while q:\n",
    "        d, node = heapq.heappop(q)\n",
    "        if d > dis[node]:\n",
    "            continue\n",
    "\n",
    "        for ch in graph[node]:\n",
    "            if d + cost[node][ch] < dis[ch]:\n",
    "                dis[ch] = d + cost[node][ch]\n",
    "                heapq.heappush(q, (dis[ch], ch))\n",
    "\n",
    "    return dis\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        cost = [{} for _ in range(n)]\n",
    "        for u, v, c in edges:\n",
    "            u -= 1\n",
    "            v -= 1\n",
    "            g[u].append(v)\n",
    "            cost[u][v] = c\n",
    "            g[v].append(u)\n",
    "            cost[v][u] = c\n",
    "\n",
    "        dis = dijkstra(g, cost, n - 1)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(node):\n",
    "            if node == n - 1:\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "            for ch in g[node]:\n",
    "                if dis[ch] < dis[node]:\n",
    "                    res += dfs(ch)\n",
    "                    res %= kmod\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        g = defaultdict(list)\n",
    "        for a, b, w in edges:\n",
    "            g[a].append((b, w))\n",
    "            g[b].append((a, w))\n",
    "        \n",
    "        dis = [inf] * (n + 1)\n",
    "        dis[n] = 0\n",
    "        q = [(0, n)]\n",
    "        vis = set()\n",
    "        while q:\n",
    "            d, node = heapq.heappop(q)\n",
    "            if node in vis:\n",
    "                continue\n",
    "            vis.add(node)\n",
    "            for y, w in g[node]:\n",
    "                if d + w < dis[y]:\n",
    "                    dis[y] = d + w\n",
    "                    heapq.heappush(q, (d + w, y))\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for y, _ in g[x]:\n",
    "                if dis[x] > dis[y]:\n",
    "                    res += dfs(y)\n",
    "            return res % mod\n",
    "        return dfs(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dijkstra(g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "    dist = [inf] * len(g)\n",
    "    dist[start] = 0\n",
    "    h = [(0, start)]\n",
    "    while h:\n",
    "        d, x = heappop(h)\n",
    "        if d > dist[x]:\n",
    "            continue\n",
    "        for y, wt in g[x]:\n",
    "            new_d = dist[x] + wt\n",
    "            if new_d < dist[y]:\n",
    "                dist[y] = new_d\n",
    "                heappush(h, (new_d, y))\n",
    "    return dist\n",
    "mod=10**9+7\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for u,v,w in edges:\n",
    "            g[u-1].append((v-1,w))\n",
    "            g[v-1].append((u-1,w))\n",
    "        dij=dijkstra(g,n-1)\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x==0:\n",
    "                return 1\n",
    "            else:\n",
    "                ans=0\n",
    "                for nx,w in g[x]:\n",
    "                    if dij[x]<dij[nx]:\n",
    "                        ans=(ans+dfs(nx))%mod\n",
    "                return ans\n",
    "        return dfs(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        @functools.lru_cache(maxsize=None) \n",
    "        def dp(cur):\n",
    "            if cur == n - 1:\n",
    "                return 1\n",
    "                \n",
    "            ans = 0 \n",
    "            for nxt, _ in graph[cur]:\n",
    "                if dist[cur] > dist[nxt]:\n",
    "                    ans = (ans + dp(nxt)) % MOD\n",
    "            return ans \n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            graph[u-1].append((v-1, w))\n",
    "            graph[v-1].append((u-1, w))\n",
    "\n",
    "        heap = [(0, n-1)]\n",
    "        dist = [math.inf] * n \n",
    "        dist[-1] = 0\n",
    "        while heap:\n",
    "            d, cur = heapq.heappop(heap) \n",
    "            if d > dist[cur]:\n",
    "                continue \n",
    "            for nxt, w in graph[cur]:\n",
    "                if d + w < dist[nxt]:\n",
    "                    dist[nxt] = d + w\n",
    "                    heapq.heappush(heap, (d + w, nxt))  \n",
    "        return dp(0) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dtl = [0]*(n+1)\n",
    "        vis = [False]*(n+1)\n",
    "        hp = [(0,n)]\n",
    "        d = defaultdict(list)\n",
    "        for a,b,w in edges:\n",
    "            d[a].append((b,w))\n",
    "            d[b].append((a,w))\n",
    "        while hp:\n",
    "            curdist, fa = heappop(hp)\n",
    "            if vis[fa]:\n",
    "                continue\n",
    "            vis[fa]=True\n",
    "            dtl[fa]=curdist\n",
    "            for node,w in d[fa]:\n",
    "                if not vis[node]:\n",
    "                    heappush(hp, (curdist+w,node))\n",
    "        MOD = 1000000007\n",
    "        @cache\n",
    "        def dfs(fa,node):\n",
    "            pre = dtl[node]\n",
    "            cnt = 0\n",
    "            if node==n:\n",
    "                return 1\n",
    "            for son, w in d[node]:\n",
    "                if son != fa and dtl[son]<pre:\n",
    "                    cnt+=dfs(node,son)\n",
    "            return cnt%MOD\n",
    "        \n",
    "        return dfs(0,1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        graph = [dict() for _ in range(n+1)]\n",
    "        \n",
    "        # 创建邻接表表示的图\n",
    "        for u, v, w in edges:\n",
    "            graph[u][v] = graph[v][u] = w\n",
    "        \n",
    "        # 使用Dijkstra算法从n计算到其他节点的最短距离\n",
    "        distance = [float('inf')] * (n+1)\n",
    "        distance[n] = 0\n",
    "        visited = set()\n",
    "        heap = [(0, n)]\n",
    "        \n",
    "        while heap:\n",
    "            d, node = heapq.heappop(heap)\n",
    "            if node in visited:\n",
    "                continue\n",
    "            visited.add(node)\n",
    "            for neigh, w in graph[node].items():\n",
    "                if distance[neigh] > d + w:\n",
    "                    distance[neigh] = d + w\n",
    "                    heapq.heappush(heap, (distance[neigh], neigh))\n",
    "        \n",
    "        # 使用DFS找出受限路径数\n",
    "        memo = {}\n",
    "        \n",
    "        def dfs(node):\n",
    "            if node == n:\n",
    "                return 1\n",
    "            if node in memo:\n",
    "                return memo[node]\n",
    "            \n",
    "            ans = 0\n",
    "            for neigh in graph[node]:\n",
    "                if distance[neigh] < distance[node]:\n",
    "                    ans += dfs(neigh)\n",
    "                    ans %= mod\n",
    "            memo[node] = ans\n",
    "            return ans\n",
    "        \n",
    "        return dfs(1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u,v,w in edges:\n",
    "            graph[u-1].append([v-1,w])\n",
    "            graph[v-1].append([u-1,w])\n",
    "        dist = [float('inf')]*n\n",
    "        dist[n-1] = 0\n",
    "        heap = []\n",
    "        heapq.heappush(heap,[0, n-1])\n",
    "        while(heap):\n",
    "            d, u = heapq.heappop(heap)\n",
    "            for v, w in graph[u]:\n",
    "                if(d + w < dist[v]):\n",
    "                    dist[v] = d + w \n",
    "                    heapq.heappush(heap, [dist[v], v])\n",
    "        @cache\n",
    "        def dfs(u, target):\n",
    "            if(u == target):\n",
    "                return 1\n",
    "            res = 0\n",
    "            for v,_ in graph[u]:\n",
    "                if(dist[u] > dist[v]):\n",
    "                    res += dfs(v, target) % (10**9+7)\n",
    "            return res % (10**9+7)\n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u,v,w in edges:\n",
    "            graph[u-1].append([v-1,w])\n",
    "            graph[v-1].append([u-1,w])\n",
    "        dist = [float('inf')]*n\n",
    "        dist[n-1] = 0\n",
    "        heap = []\n",
    "        heapq.heappush(heap,[0, n-1])\n",
    "        while(heap):\n",
    "            d, u = heapq.heappop(heap)\n",
    "            for v, w in graph[u]:\n",
    "                if(d + w < dist[v]):\n",
    "                    dist[v] = d + w \n",
    "                    heapq.heappush(heap, [dist[v], v])\n",
    "        @cache\n",
    "        def dfs(u, target):\n",
    "            if(u == target):\n",
    "                return 1\n",
    "            res = 0\n",
    "            for v,_ in graph[u]:\n",
    "                if(dist[u] > dist[v]):\n",
    "                    res += dfs(v, target)\n",
    "            return res % (10**9+7)\n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u,v,w in edges:\n",
    "            graph[u-1].append([v-1,w])\n",
    "            graph[v-1].append([u-1,w])\n",
    "        dist = [float('inf')]*n\n",
    "        dist[n-1] = 0\n",
    "        heap = []\n",
    "        heapq.heappush(heap,[0, n-1])\n",
    "        while(heap):\n",
    "            d, u = heapq.heappop(heap)\n",
    "            for v, w in graph[u]:\n",
    "                if(d + w < dist[v]):\n",
    "                    dist[v] = d + w \n",
    "                    heapq.heappush(heap, [dist[v], v])\n",
    "        @cache\n",
    "        def dfs(u, target):\n",
    "            if(u == target):\n",
    "                return 1\n",
    "            res = 0\n",
    "            for v,_ in graph[u]:\n",
    "                if(dist[u] > dist[v]):\n",
    "                    res += dfs(v, target)\n",
    "            return res % (10**9+7)\n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u,v,w in edges:\n",
    "            graph[u-1].append([v-1,w])\n",
    "            graph[v-1].append([u-1,w])\n",
    "        dist = [float('inf')]*n\n",
    "        dist[n-1] = 0\n",
    "        heap = []\n",
    "        heapq.heappush(heap,[0, n-1])\n",
    "        while(heap):\n",
    "            d, u = heapq.heappop(heap)\n",
    "            for v, w in graph[u]:\n",
    "                if(d + w < dist[v]):\n",
    "                    dist[v] = d + w \n",
    "                    heapq.heappush(heap, [dist[v], v])\n",
    "        @cache\n",
    "        def dfs(u, target):\n",
    "            if(u == target):\n",
    "                return 1\n",
    "            res = 0\n",
    "            for v,_ in graph[u]:\n",
    "                if(dist[u] > dist[v]):\n",
    "                    res += dfs(v, target) % (10**9+7)\n",
    "            return res % (10**9+7)\n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        d=[inf]*n\n",
    "        m=10**9+7\n",
    "        e=[[]for _ in range(n)]\n",
    "        for a, b,w in edges:\n",
    "            e[a-1].append((b-1,w))\n",
    "            e[b-1].append((a-1,w))\n",
    "        d[-1]=0\n",
    "        q=[(0,n-1)]\n",
    "        while q:\n",
    "            dis,j=heappop(q)\n",
    "            for k,w in e[j]:\n",
    "                dk=dis+w\n",
    "                if d[k]>dk:\n",
    "                    d[k]=dk\n",
    "                    heappush(q,(dk,k))\n",
    "        @cache\n",
    "        def dfs(i,p):\n",
    "            if i==n-1:return 1\n",
    "            s=0\n",
    "            for j,_ in e[i]:\n",
    "                if j!=p and d[i]>d[j]:\n",
    "                    s=(s+dfs(j,i))%m\n",
    "            return s\n",
    "        return dfs(0,-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        d=[inf]*n\n",
    "        m=10**9+7\n",
    "        e=[[]for _ in range(n)]\n",
    "        for a, b,w in edges:\n",
    "            e[a-1].append((b-1,w))\n",
    "            e[b-1].append((a-1,w))\n",
    "        d[-1]=0\n",
    "        q=[(0,n-1)]\n",
    "        #print(e)\n",
    "        while q:\n",
    "            dis,j=heappop(q)\n",
    "            #print(dis,j)\n",
    "            for k,w in e[j]:\n",
    "                dk=dis+w\n",
    "                #print(dk,d[k])\n",
    "                if d[k]>dk:\n",
    "                    d[k]=dk\n",
    "                    heappush(q,(dk,k))\n",
    "        @cache\n",
    "        def dfs(i,p):\n",
    "            if i==n-1:return 1\n",
    "            s=0\n",
    "            for j,_ in e[i]:\n",
    "                if j!=p and d[i]>d[j]:\n",
    "                    s=(s+dfs(j,i))%m\n",
    "            return s\n",
    "        return dfs(0,-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 1000000007\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[]for i in range(n+1)]\n",
    "        d = [inf]*(n+1)\n",
    "        for u,v,w in edges:\n",
    "\n",
    "            g[u].append((v,w))\n",
    "            g[v].append((u,w))\n",
    "        @cache\n",
    "        def ws(u,v):\n",
    "            for x,y in g[u]:\n",
    "                if x == v:\n",
    "                    return y\n",
    "            \n",
    "        q = []\n",
    "        heappush(q,(0,n))\n",
    "        while len(q)>0:\n",
    "            dis,u = heappop(q)\n",
    "            if d[u] != inf:\n",
    "                continue\n",
    "            d[u] = dis\n",
    "            for v,_ in g[u]:\n",
    "\n",
    "                if d[v] == inf:\n",
    "                    heappush(q,(dis+ws(u,v), v))\n",
    "\n",
    "        @cache\n",
    "        def f(u):\n",
    "            if u == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for v,_ in g[u]:\n",
    "                if d[v] < d[u]:\n",
    "                    res += f(v)\n",
    "            return res%mod\n",
    "        return f(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph, MOD, heap, dist = defaultdict(lambda: defaultdict(int)), 10 ** 9 + 7, [(0, n - 1)], [inf] * (n - 1) + [0]\n",
    "        for u, v, w in edges:\n",
    "            graph[u - 1][v - 1] = graph[v - 1][u - 1] = w\n",
    "        while heap:\n",
    "            d, x = heappop(heap)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, w in graph[x].items():\n",
    "                if (cur := dist[x] + w) < dist[y]:\n",
    "                    dist[y] = cur\n",
    "                    heappush(heap, (cur, y))\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x: int) -> int:\n",
    "            if not x:\n",
    "                return 1\n",
    "            else:\n",
    "                result = 0\n",
    "                for y in graph[x]:\n",
    "                    if dist[y] > dist[x]:\n",
    "                        result += dfs(y)\n",
    "            return result % MOD\n",
    "        return dfs(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val, dis) -> None:\n",
    "        self.val = val\n",
    "        self.dis = dis\n",
    "    def __lt__(self, other) -> bool:\n",
    "        return self.dis < other.dis\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            graph[u - 1].append([v - 1, w])\n",
    "            graph[v - 1].append([u - 1, w])\n",
    "        dis = [inf] * n\n",
    "        dis[-1] = 0\n",
    "        def dijkstra():\n",
    "            vis = [False] * n\n",
    "            h = [Node(n - 1, 0)]\n",
    "            while len(h) > 0:\n",
    "                top = heappop(h)\n",
    "                if vis[top.val]:\n",
    "                    continue\n",
    "                for e in graph[top.val]:\n",
    "                    if dis[e[0]] > dis[top.val] + e[1]:\n",
    "                        dis[e[0]] = dis[top.val] + e[1]\n",
    "                        heappush(h, Node(e[0], dis[e[0]]))\n",
    "        dijkstra() \n",
    "        @cache\n",
    "        def dfs(root, fa):\n",
    "            ans = 1 if root == n - 1 else 0\n",
    "            for e in graph[root]:\n",
    "                if e[0] == fa or dis[e[0]] >= dis[root]:\n",
    "                    continue\n",
    "                ans += dfs(e[0], root) % MOD\n",
    "            return ans\n",
    "        return dfs(0, -1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Dijkstra:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_dijkstra_result(dct: List[List[int]], src: int) -> List[float]:\n",
    "        # 模板: Dijkstra求最短路，变成负数求可以求最长路（还是正权值）\n",
    "        n = len(dct)\n",
    "        dis = [inf]*n\n",
    "        stack = [[0, src]]\n",
    "        dis[src] = 0\n",
    "\n",
    "        while stack:\n",
    "            d, i = heapq.heappop(stack)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j, w in dct[i]:\n",
    "                dj = w + d\n",
    "                if dj < dis[j]:\n",
    "                    dis[j] = dj\n",
    "                    heapq.heappush(stack, [dj, j])\n",
    "        return dis\n",
    "    \n",
    "    \n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j, w in edges:\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "            dct[i].append([j, w])\n",
    "            dct[j].append([i, w])\n",
    "        dis = Dijkstra().get_dijkstra_result(dct, n-1)\n",
    "\n",
    "        new = [[] for _ in range(n)]\n",
    "        cnt = [0]*n\n",
    "        degree = [0]*n\n",
    "        for i, j, w in edges:\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "            if dis[i] > dis[j]:\n",
    "                new[i].append(j)\n",
    "                degree[j] += 1\n",
    "            if dis[j] > dis[i]:\n",
    "                new[j].append(i)\n",
    "                degree[i] += 1\n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            if x == n-1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for y in new[x]:\n",
    "                res += dfs(y)\n",
    "            return res % mod\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 1000000007\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[]for i in range(n+1)]\n",
    "        d = [inf]*(n+1)\n",
    "        ws = {}\n",
    "        for u,v,w in edges:\n",
    "            ws[(u,v)] = ws[(v,u)] = w\n",
    "            g[u].append((v,w))\n",
    "            g[v].append((u,w))\n",
    "            \n",
    "        q = []\n",
    "        heappush(q,(0,n))\n",
    "        while len(q)>0:\n",
    "            dis,u = heappop(q)\n",
    "            if d[u] != inf:\n",
    "                continue\n",
    "            d[u] = dis\n",
    "            for v,_ in g[u]:\n",
    "\n",
    "                if d[v] == inf:\n",
    "                    heappush(q,(dis+ws[(u,v)], v))\n",
    "\n",
    "        @cache\n",
    "        def f(u):\n",
    "            if u == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for v,_ in g[u]:\n",
    "                if d[v] < d[u]:\n",
    "                    res += f(v)\n",
    "            return res%mod\n",
    "        return f(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 1000000007\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[]for i in range(n+1)]\n",
    "        d = [inf]*(n+1)\n",
    "        ww = {}\n",
    "        for u,v,w in edges:\n",
    "            ww[(u,v)] = ww[(v,u)] = w\n",
    "            g[u].append((v,w))\n",
    "            g[v].append((u,w))\n",
    "            \n",
    "        def ws(u,v):\n",
    "            return ww[(u,v)]\n",
    "            \n",
    "        q = []\n",
    "        heappush(q,(0,n))\n",
    "        while len(q)>0:\n",
    "            dis,u = heappop(q)\n",
    "            if d[u] != inf:\n",
    "                continue\n",
    "            d[u] = dis\n",
    "            for v,_ in g[u]:\n",
    "\n",
    "                if d[v] == inf:\n",
    "                    heappush(q,(dis+ws(u,v), v))\n",
    "\n",
    "        @cache\n",
    "        def f(u):\n",
    "            if u == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for v,_ in g[u]:\n",
    "                if d[v] < d[u]:\n",
    "                    res += f(v)\n",
    "            return res%mod\n",
    "        return f(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = []\n",
    "        for i in range(n + 1): graph.append([])\n",
    "        for e in edges:\n",
    "            graph[e[0]].append([e[1], e[2]])\n",
    "            graph[e[1]].append([e[0], e[2]])\n",
    "        \n",
    "        dis = [10**10] * (n + 1)\n",
    "        vis = [False] * (n + 1)\n",
    "        queue = [[0, n]]\n",
    "        dis[n] = 0\n",
    "        while queue:\n",
    "            temp, idx = heapq.heappop(queue)\n",
    "            if vis[idx]: continue\n",
    "            vis[idx] = True\n",
    "            for nxt, val in graph[idx]:\n",
    "                if not vis[nxt] and dis[nxt] > temp + val:\n",
    "                    dis[nxt] = temp + val\n",
    "                    heapq.heappush(queue, [dis[nxt], nxt])\n",
    "        \n",
    "        record = [0] * (n + 1)\n",
    "        def dfs(cur):\n",
    "            if record[cur] > 0:\n",
    "                return record[cur]\n",
    "            if cur == n:\n",
    "                return 1\n",
    "            for nxt, _ in graph[cur]:\n",
    "                if dis[nxt] < dis[cur]:\n",
    "                    record[cur] += dfs(nxt)\n",
    "            return record[cur]\n",
    "        return dfs(1) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[[] for i in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x-1].append([y-1,w])\n",
    "            g[y-1].append([x-1,w])\n",
    "\n",
    "        dis=[inf for i in range(n)]\n",
    "        dis[n-1]=0\n",
    "\n",
    "        h=[(0,n-1)]\n",
    "        heapify(h)\n",
    "        vis=[False]*n\n",
    "        while h:\n",
    "            d,x=heappop(h)\n",
    "            if vis[x]:\n",
    "                continue\n",
    "            vis[x]=True\n",
    "            dis[x]=d\n",
    "            for y,w in g[x]:\n",
    "                if dis[x]+w<dis[y]:\n",
    "                    heappush(h,(dis[x]+w,y))     \n",
    "\n",
    "\n",
    "        \n",
    "        g=[[] for i in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            if dis[x-1]==dis[y-1]:\n",
    "                continue\n",
    "            if dis[x-1]<dis[y-1]:\n",
    "                g[y-1].append(x-1)\n",
    "            else:\n",
    "                g[x-1].append(y-1)\n",
    "            \n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x==n-1:\n",
    "                return 1\n",
    "            res=0\n",
    "            for y in g[x]:\n",
    "                res+=dfs(y)\n",
    "            return res\n",
    "\n",
    "        return dfs(0)%(10**9+7)\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[[] for i in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x-1].append([y-1,w])\n",
    "            g[y-1].append([x-1,w])\n",
    "\n",
    "        dis=[inf for i in range(n)]\n",
    "        dis[n-1]=0\n",
    "\n",
    "        h=[(0,n-1)]\n",
    "        heapify(h)\n",
    "        vis=[False]*n\n",
    "        while h:\n",
    "            d,x=heappop(h)\n",
    "            if vis[x]:\n",
    "                continue\n",
    "            vis[x]=True\n",
    "            dis[x]=d\n",
    "            for y,w in g[x]:\n",
    "                if dis[x]+w<dis[y]:\n",
    "                    heappush(h,(dis[x]+w,y))     \n",
    "\n",
    "        g=[[] for i in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            if dis[x-1]==dis[y-1]:\n",
    "                continue\n",
    "            if dis[x-1]<dis[y-1]:\n",
    "                g[y-1].append(x-1)\n",
    "            else:\n",
    "                g[x-1].append(y-1)\n",
    "            \n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x==n-1:\n",
    "                return 1\n",
    "            res=0\n",
    "            for y in g[x]:\n",
    "                res+=dfs(y)\n",
    "            return res\n",
    "\n",
    "        return dfs(0)%(10**9+7)\n",
    "        \n",
    "\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
